1. Technical Field
This invention is directed toward a system and process for adaptive document layout. More particularly, this invention is directed toward a system and process for adapting document layouts to devices of different resolutions and sizes.
2. Background Art
Paper documents are, by their very nature, static affairs. Their physical nature confines them to a single immutable layout on a single-size sheet of paper. Electronic documents, by contrast, can and should be much more dynamic. Most importantly, they should adapt seamlessly and attractively to the size and proportions of the display on which they appear—be it a standard monitor, a tiny Personal Data Assistant (PDA) screen, or a certain format of paper. In addition, the dynamic nature of an electronic medium should offer the possibility of adapting the content dynamically for a particular type of reader or reading situation—providing a summary view for one reader and an in-depth view for another.
Electronic documents today fall woefully short of these ideals. In general, they provide an impoverished layout in comparison with their traditional, physical counterparts. Moreover, they provide only an exceedingly limited ability to adapt to different displays. Typically, either the width of the text is expanded to fill the available window or screen, in which case the text quickly becomes illegible—or the text area is kept fixed, which solves the first problem but requires inconvenient scrolling whenever the text area is too large for the target display. Indeed, to address these shortcomings, in practice two distinct versions of a document are often supplied: a Portable Document File (PDF) version, which generally includes more carefully thought-out design elements and layout, but at the expense of nearly all adaptability; and a Hypertext Markup Language (HTML) version, which is generally easier to read on most standard-sized screens, but whose graphics and layout are meager in comparison with those of the PDF.
Good automatic and adaptive layout is fundamentally hard. Consider, for example, a document with a single, large, multicolumn sidebar. The sidebar may look fine on the right side of a two-page spread or a wide-screen display. But on a legal-sized sheet of paper or on a portrait display, the “sidebar” may actually have to be placed at the bottom of the page so as not to squeeze out the main story. And on a PDA, this same “sidebar” might have to be moved to a separate page entirely, perhaps made available through an HTML link from the main page. The problem is of course compounded for more complex layouts, such as those involving multiple sidebars, figures, pull quotes, and so on-all being merged into a single page design.
Even more tricky, in many respects, is the need for editorial changes to content to make a given layout work. As Knuth, in some of his seminal work on typesetting, acknowledges, a “computer should, in fact, be able to solve the typesetting problem better than a skilled typesetter could do by hand in a reasonable amount of time—unless we give this person the liberty to change the wording in order to obtain a better fit” [8] (emphasis added). As any person who has ever prepared a technical paper submission (or any other camera-ready document) knows, often one is forced to make last-minute changes to the figures or text in order to, say, squeeze everything into the stringent page limits, produce more favorable juxtapositions of figures and text, or eliminate annoying “widows” or “orphans” (single lines of text that are separated from their paragraphs and appear alone at the top or bottom of a page or column).
One might add that this inability to adapt document layouts to different display sizes is becoming a more and more critical problem, as the variety of new and differently sized display devices proliferates. The problem is also exacerbated, in a sense, by the rapidly increasing screen resolutions available on LCD displays. These displays make practical increasingly complex page layouts and graphical designs that come closer all the time to rivaling those that can be rendered on the printed page. Thus, any deficit in the available quality of documents rendered on the screen versus the printed page becomes all the more apparent and egregious.
Early work in document layout focused largely on text formatting, the arrangement of text into lines, paragraphs, and higher-level semantic structures [6, 8, 10]. More recently, researchers have begun to focus on the page layout problem, whereby relational grammars [11], constraints [1, 2, 3, 4, 5], or various forms of optimization [13] are used to arrange different elements onto a page while satisfying some notion of “goodness.” Recently, several standards, endorsed by the World-Wide-Web Consortium (W3C), have emerged to support the decoupling of a document's content from its stylistic formatting rules, most notably the Extensible Stylesheet Language (XSL) and Cascading Style Sheets (CSS) [9]. A constraint-based version of Cascading Style Sheets (CCSS) has also been proposed [1].
It is noted that in the preceding paragraphs, as well as in the remainder of this specification, the description refers to various individual publications identified by a numeric designator contained within a pair of brackets. For example, such a reference may be identified by reciting, “reference [1]” or simply “[1]”. A listing of the publications corresponding to each designator can be found at the end of the Detailed Description section.